/**
 * 复杂度的几种表达式
 *
 * 属于P问题，99%可以遇见
 * O(1) 常数级
 * O(log(n)) 指数级
 * O(n) 线性级
 * O(n^2) 指数级
 *
 *  属于NP问题,不常见
 * O(2^n) 级数级
 *
 *
 */

/**
 *
 * 有序数组的二分查找法时间复杂度是O(log(n))
 *
 * 定义函数实现二分查找
 *
 */

function findIndexByOrderArray(arr: number[], value: number): number {
  //定义起点和终点
  let start: number = 0;
  let end: number = arr.length - 1;

  // 终止条件:直到start大于end,表示没找到,否则一直循环
  while (start <= end) {
    let center: number = Math.floor(start + end);
    if (arr[center] == value) {
      return center;
    } else if (arr[center] > value) {
      //相当于右边的数组废了; 移动 end下标位置
      end = center - 1;
    } else {
      //相当于左边的数组废了; 移动 start下标位置
      start = center + 1;
    }
  }

  // 没找到返回-1
  return -1;
}

let arr = [1, 3, 4, 5, 6, 7, 8, 9, 34, 56, 78, 122];

console.log(findIndexByOrderArray(arr, 8));
